package LeetCode.month01.day03;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;

public class No76 {
    public static void main(String[] args) {
        String s = "aAabBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";
        String t = "aAabBcCdDeEfFgGhiHIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";
        System.out.println(minWindow(s, t));
    }

    /*
    acsdfbsdba;
    acsdfbsdab;
    ab
    队列为空
    当前字符是要求字符，对应map中的数量减一.
    队列非空
    当前字符是要求字符，且数量非零，插入队列，对应map数量减一，
    当前字符是要求字符，且数量小于等于零，
        判断队头元素是否是该字符，
            是就挨个抛出不是要求的字符，直到队头元素是要求字符，且要求字符的数量得大于等于零，否则抛出要求字符，
            不是该字符，就插入队列，且对应map数量减一，
    当前字符不是要求字符，直接加入队列，

     */

    public static String minWindow(String s, String t) {
        if(t.length()>s.length()) return "";
        //s= s.toLowerCase();
        //t= t.toLowerCase();
        //System.out.println(s);
        HashMap<Character,Integer> map = new HashMap<>();
        int num = t.length();
        int left = 0,right=s.length();
        for (int i = 0; i < t.length(); i++) {
            map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0)+1);
        }
        //System.out.println(map);
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            //System.out.print(i+":");
            if(deque.isEmpty()&&map.containsKey(s.charAt(i))) { //队列为空且当前字符是要求字符
                //System.out.print("当前字符为"+s.charAt(i)+"队列为空，且是要求字符  ");
                deque.add(i);
                map.put(s.charAt(i),map.get(s.charAt(i))-1);
                num--;
                //System.out.print(" 当前队列:"+deque);
                //System.out.println(" 剩余字符"+map);

            }else if(!deque.isEmpty()){       //队列非空
                if(!map.containsKey(s.charAt(i))){      //当前字符不是要求字符
                    //System.out.print("队列非空，当前字符为"+s.charAt(i)+"不是要求字符");
                    deque.add(i);
                    //System.out.print(" 当前队列:"+deque);
                    //System.out.println(" 剩余字符"+map);
                }else{          //当前字符是要求字符
                    if(map.get(s.charAt(i))>0){     //要求字符数量大于0
                        //System.out.print("队列非空，当前字符为"+s.charAt(i)+"是要求字符，且字符数量大于0");
                        deque.add(i);
                        map.put(s.charAt(i),map.get(s.charAt(i))-1);
                        num--;
                        //System.out.print(" 当前队列:"+deque);
                        //System.out.println(" 剩余字符"+map);
                    }else{          //要求字符数量小于等于0
                        if(s.charAt(deque.getFirst())==s.charAt(i)){        //当前字符与队头字符相同
                            //System.out.print("队列非空，当前字符为"+s.charAt(i)+"是要求字符，且字符数量小于等于0，当前字符与队头字符相同，进行循环");
                            deque.add(i);
                            deque.pollFirst();
                            while(!map.containsKey(s.charAt(deque.getFirst()))||(map.containsKey(s.charAt(deque.getFirst()))&&map.get(s.charAt(deque.getFirst()))<0)){    //抛出
                                if(map.containsKey(s.charAt(deque.getFirst()))){
                                    map.put(s.charAt(deque.getFirst()),map.get(s.charAt(deque.getFirst()))+1);
                                }
                                deque.pollFirst();
                            }
                            //System.out.print(" 当前队列:"+deque);
                            //System.out.println(" 剩余字符"+map);
                        }else{          //当前字符与队头字符不同
                            //System.out.print("队列非空，当前字符为"+s.charAt(i)+"是要求字符，且字符数量小于等于0，当前字符与队头字符不相同");
                            deque.add(i);
                            map.put(s.charAt(i),map.get(s.charAt(i))-1);
                            //System.out.print(" 当前队列:"+deque);
                            //System.out.println(" 剩余字符"+map);
                        }
                    }
                }
            }
            if(num==0&&deque.getLast()-deque.getFirst()<right-left) {
                left = deque.getFirst();
                right = deque.getLast();
            }
        }
        //System.out.println(deque);
        //System.out.println(map);
        for (int value :map.values()){
            if(value>0) return "";
        }
        while(!map.containsKey(s.charAt(deque.getLast()))){
            deque.pollLast();
        }
        return right-left>deque.getLast()-deque.getFirst()?
                s.substring(deque.getFirst(),deque.getLast()+1):
                s.substring(left,right+1);
    }
}
